/*
 * @lc app=leetcode.cn id=145 lang=csharp
 *
 * [145] 二叉树的后序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        IList<int> ans = new List<int>();

        while (current != null || stack.Count > 0)
        {
            if (current != null)
            {
                stack.Push(current);
                current = current.left != null ? current.left : current.right;
            }
            // 1.右孩子为空了(执行到else 一定是右孩子为空，右孩子为空那根据三目表达式，左孩子也为空。也即是栈顶为叶子节点.)
            // 2.先打印这个节点，然后判断此节点是其父节点的左孩子还是右孩子。
            //  3.如果是右孩子，则current 指向右孩子。然后重复2（也即判断刚打印节点的父节点是其爷爷节点的右孩子还是左孩子）。
            //  4.如果是左孩子则 current 指向其父节点的右孩子，继续重复。
            else
            {
                current = stack.Pop();
                ans.Add(current.val);

                // 如果当前节点是其父节点的右孩子,则打印父节点
                while (stack.Count > 0 && current != stack.Peek().left)
                {
                    current = stack.Pop();
                    ans.Add(current.val);
                }
                if (stack.Count == 0)
                {
                    break;
                }
                // 如果当前节点是其父节点的左孩子， 则转到父节点的右孩子继续遍历
                if (current == stack.Peek().left)
                {
                    current = stack.Peek().right;
                }
            }
        }
        return ans;
    }
    
    
}
// @lc code=end

